The invention relates to medium access controls, and more particularly, to contention window adjustment methods capable of Load-Adaptive Backoff (LAB for short) in a network.
The media access control (MAC) protocol defines data transferring methods for stations (communication devices, such as laptops, personal digital assistants, mobile phones, and others) in a medium-shared network. The station following a carrier sense multiple access (CSMA for short) protocol must detect whether the medium is busy before sending a frame. Networks with MAC methods based on CSMA comprise wireless local area networks (WLAN) conforming to the Institute of Electrical and Electronic Engineers (IEEE) 802.11 standard, ultra wideband (UWB) networks conforming to IEEE 802.15.3 standard, wireless sensor networks (WSNs) conforming to the IEEE 802.15.4 standard, Ethernets conforming to the IEEE 802.3 standard, and others. Several MAC methods, including IEEE 802.3, 802.11, 802.15.3, and 802.15.4 standards, utilize the Binary Exponential Backoff (BEB) algorithm to adjust the contention window (CW) to avoid or resolve collisions.
In this invention, we take IEEE 802.11 for example to describe the operations of BEB. IEEE 802.11 defines two access functions: one is distributed coordination functions (DCF), and the other is point coordination functions (PCF). Stations complying with the wireless fidelity (Wi-Fi) specification must support DCF. DCF employs the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) method to transmit frames. If station A wants to send a data frame to station B, then station A should sense the medium before sending a frame. However, even if the medium is idle at this moment, station A cannot immediately transmit a frame. Station A must wait for a period of “DCF Inter Frame Space (DIFS)” time. After the DIFS time passing, station A can transmit data frames. On the other hand, if the medium is busy when station A wants to transmit, then station A defers until the medium is determined to be idle for DIFS, and then station A selects the backoff slots whose number is a random integer between zero and CW−1, where CW denotes the contention window. The backoff time decreases continuously by one slot. It is noteworthy that backoff countdown process may not be always successful. If the medium is determined busy at any time during a backoff slot, then the backoff timer should be frozen. When the channel is sensed idle again for more than a DIFS, the backoff timer can be reactivated. Whenever the backoff timer reaches zero, transmission shall commence. The effect of this DCF procedure is that when multiple stations enter the backoff stage at the same time, then the station choosing the minimum backoff time will win the contention. Upon reception of the data frame, the destination station (station B) shall reply the ACK frame after an elapsed SIFS (Short InterFrame Space). Note that SIFS<DIFS. If the sending station does not hear the ACK signal, it shall resend the data frame after waiting at least an ACK timeout interval or drops that frame when the DCF retry limit is reached. By the 802.11 standard, the backoff time is defined as follows.BackoffTime=DUR(0,CW)*SlotTime, CWS=CW−1,where DUR(0,CW) is a function which will return an integer randomly and uniformly between 0 and CW−1. Notice that CW and SlotTime are PHY(physical layer)-specific. For example, when the PHY is Direct Sequence Spread Spectrum (DSSS) defined in IEEE 802.11b, then SlotTime is 20 μs and the possible value of CWS(CW+1) is 32, 64, 128, 256, 512, or 1024.
To resolve collisions, DCF employs BEB and its corresponding retransmission method. FIG. 1 is a schematic view of CWS adjustment using BEB. The values of the maximum contention window (CWmax) and the minimum contention window (CWmin) are defined in 802.11. Notice that we define that CWS=CW+1, CWSmax=CWmax+1, and CWSmin=CWmin+1 for convenience. Based on BEB, whenever data frame transmission fails, the value of CWS is doubled until CWS equals CWSmax. Once the data frame transmission succeeds, the value of CWS jumps to CWSmin directly.
The drawbacks of BEB are as follows. Even if a station fails to transmit a data frame many times, the value of CW will reduce to CWmin once that station successfully transmit a data frame. We believe that this CW value (CWmin) is too small since the medium contention may be still severe. The inadequate CW value (CWmin) may incur more collisions, causing the throughput down. In addition, the collided station has a larger CW value, which makes it more difficult to seize the medium than a non-collided station (whose CW value is CWmin). In other words, collided stations have lower chance to seize the medium. Therefore, BEB cannot support short-term fairness among contending stations.
To support Quality of Service, IEEE 802.11 Task Group E is struggling for defining the 802.11e standard. 802.11e assigns different values of CWmax and CWmin for different priority access categories. In particular, a higher priority station has smaller values of CWmax and CWmin. Regardless of the priority, the station in 802.11e still follows the BEB to transmit data frames. This implies that the above-mentioned problems may still occur in 802.11e.
As described, the invention discloses a contention window adjustment method capable of load-adaptive backoff (LAB). Compared with BEB, LAB can appropriately adjust the value of CW (CWS) according to traffic load in a network, significantly reducing the collision probability and data transmission delay, thus improving throughput and fairness.